package suanfa;

import java.util.*;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2024/9/20-上午9:14
 * Since  :   1.0
 * Version:   1.0
 */
public class Linked {

    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        TreeNode temp = root;
        while (temp != null) {
            result.add(temp.val);
            if (temp.left == null && temp.right == null) {
                break;
            } else if (temp.right != null) {
                temp = temp.right;
            } else {
                temp = temp.left;
            }

        }
        return result;


    }

    public static List<Double> averageOfLevels(TreeNode root) {
        ArrayList<Integer> count = new ArrayList<>();
        ArrayList<Double> sums = new ArrayList<>();

        dfs(root, 0, count, sums);
        ArrayList<Double> results = new ArrayList<>();
        for (int i = 0; i < count.size(); i++) {
            results.add(sums.get(i) / count.get(i));
        }

        return results;


    }


    public static void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
        if (root == null) {
            return;
        }
        if (level < sums.size()) {
            sums.set(level, sums.get(level) + root.val);
            counts.set(level, counts.get(level) + 1);
        } else {
            sums.add(1.0 * root.val);
            counts.add(1);
        }
        dfs(root.left, level + 1, counts, sums);
        dfs(root.right, level + 1, counts, sums);
    }

    public List<Double> averageOfLevels2(TreeNode root) {
        ArrayList<Integer> counts = new ArrayList<>();
        ArrayList<Double> sums = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Double> result = new ArrayList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            double sum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                sum += temp.val;
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }


            }
            result.add(sum / size);
        }


        return result;
    }


    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> results = new ArrayList<>();
        if (root == null) {
            return results;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                result.add(temp.val);
                if (temp.left != null)
                    queue.add(temp.left);
                if (temp.right != null)
                    queue.add(temp.right);
            }
            results.add(result);

        }

        return results;
    }

    public static List<Integer> rightSideView2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                if (i == size - 1) {
                    result.add(temp.val);
                }
                if (temp.left != null)
                    queue.add(temp.left);
                if (temp.right != null)
                    queue.add(temp.right);
            }


        }
        return result;

    }


    public static void midOrder(TreeNode root, List<Integer> order) {
        if (root == null) {
            return;
        }
        midOrder(root.left, order);
        order.add(root.val);
        midOrder(root.right, order);

    }


    public static int getMinimumDifference(TreeNode root) {
        int result = Integer.MAX_VALUE;
        List<Integer> order = new ArrayList<>();
        midOrder(root, order);
        for (int i = 0; i < order.size() - 1; i++) {
            int curResult = order.get(i + 1) - order.get(i);
            result = Math.min(curResult, result);
        }

        return result;

    }

    public int kthSmallest(TreeNode root, int k) {
        List<Integer> order = new ArrayList<>();
        midOrder(root, order);
        return order.get(k - 1);
    }

    public boolean isValidBST(TreeNode root) {

        List<Integer> order = new ArrayList<>();
        midOrder(root, order);
        for (int i = 0; i < order.size() - 1; i++) {
            if (order.get(i + 1) <= order.get(i))
                return false;

        }
        return true;
    }

    public static String[] findZiMU(String end) {
        String result[]=null;
        if ("2".equals(end)) {
             result = new String[]{"a", "b", "c"};
        }
        if ("3".equals(end)) {
            result = new String[] {"d", "e", "f"};
        }
        if ("4".equals(end)) {
            result = new String[] {"g", "h", "i"};
        }
        if ("5".equals(end)) {
            result = new String[]{"j", "k", "l"};
        }
        if ("6".equals(end)) {
            result = new String[] {"m", "n", "o"};
        }
        if ("7".equals(end)) {
            result = new String[]{"p", "q", "r", "s"};
        }
        if ("8".equals(end)) {
            result = new String[]{"t", "u", "v"};
        }
        if ("9".equals(end)) {
            result = new String[] {"w", "x", "y", "z"};
        }
        return result;
    }

    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        char[] charArray = digits.toCharArray();
        if (digits.length() == 0) {
            return result;
        }
        String[] ziMU = findZiMU(charArray[0] + "");
        for (String s : ziMU) {
            result.add(s);
        }
        for (int i = 1; i < digits.length(); i++) {
            String[] Cur = findZiMU(charArray[i] + "");
            List<String> curString = new ArrayList<>();
            for (int j = 0; j < result.size(); j++) {
                for (int k = 0; k < Cur.length; k++) {
                    String temp = result.get(j) + Cur[k];
                    curString.add(temp);
                }

            }
            result = curString;
        }
        return result;

    }

    //[4,2,6,1,3]
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root4 = new TreeNode(4);
        TreeNode root5 = new TreeNode(5);
        TreeNode root6 = new TreeNode(6);
//        root1.left = root2;
//        root1.right = root3;
//        root2.right=root5;
////        root3.right=root4;
//        List<Integer> list = rightSideView(root1);
//      list.forEach(i-> System.out.println(i));

//        List<Double> doubles = averageOfLevels(root1);
//        doubles.forEach(myDouble -> System.out.println(myDouble));
//        root4.left = root2;
//        root4.right = root6;
//        root2.left = root1;
//        root2.right = root3;
//        System.out.println(getMinimumDifference(root4));

//        midOrder(root4);
//        TreeNode root0 = new TreeNode(0);
//        TreeNode root12 = new TreeNode(12);
//        TreeNode root48 = new TreeNode(48);
//        TreeNode root49 = new TreeNode(49);
//        root1.left = root0;
//        root1.right = root48;
//        root48.left = root12;
//        root48.right = root49;
//        System.out.println(getMinimumDifference(root1));
        String s = "2";
        List<String> list = letterCombinations(s);
        list.forEach(item -> System.out.println(item));


    }
}
